1768B - Quick Sort - CodeForces Solution

import math
from multiprocessing import current_process
import os
import random
import re
import copy
import pdb
import sys





        

        








if __name__ == '__main__':
    t = int(input())

    for _ in range(t):
        [n, k] = list(map(int, str(input()).split(' ')))
        
        p = list(map(int, str(input()).split(' ')))

        dict = {}

        for idx, ele in enumerate(p):
            dict[ele] = idx

        check = True
        broken = -1
        prev = dict[1]
        for i in range(2, n+1):
            loc = dict[i]
            if loc < prev:
                check = False
                broken = i
                break
            
            prev = loc

        if check == True:
            print(0)
        
        else:
            res = int((n-broken+1)/k)
            if (n-broken+1) % k != 0:
                res += 1
            print(res)